package com.lfg.leetcode.leetcode0;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class No46permute {

    public static void main(String[] args) {
        List<List<Integer>> ret = permute(new int[]{1, 2, 3});
        System.out.println(ret);
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (nums.length < 1) {
            return ret;
        }
        LinkedList<Integer> numList = new LinkedList<Integer>();
        for (int i : nums) {
            numList.add(i);
        }
        permute(new ArrayList<Integer>(), numList, ret);
        return ret;
    }

    public static void permute(List<Integer> list, LinkedList<Integer> nums, List<List<Integer>> ret) {
        int size = nums.size();
        if (size == 0) {
            List<Integer> l = new ArrayList<>();
            l.addAll(list);
            ret.add(l);
            return;
        }
        for (int i = 0; i < size; i++) {
            Integer element = nums.remove(i);
            list.add(element);
            permute(list, nums, ret);
            list.remove(list.size() - 1);
            nums.add(i, element);
        }
    }
}

